package com.cjl.interview150.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class GraphPractice {

    // 利用hash表映射访问过的节点
    HashMap<Node, Node> visited = new HashMap<>();
    /**
     * 133. 克隆图
     * @param node
     * @return
     */
    public Node cloneGraph(Node node) {
        // 非空判断
        if (node == null) {
            return node;
        }
        // 判断该节点有没有访问过
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        // 克隆节点并存入hash表
        Node newNode = new Node(node.val, new ArrayList<>());
        visited.put(node, newNode);
        // 递归跟新邻居节点
        for (Node neighbor : node.neighbors) {
            newNode.neighbors.add(cloneGraph(neighbor));
        }
        return newNode;
    }



}


class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}